package com.zdp.leetcodeMiddle;
/*
* 给你一个整数数组 arr 和一个整数 k。
首先，我们要对该数组进行修改，即把原数组 arr 重复 k 次。
举个例子，如果 arr = [1, 2] 且 k = 3，那么修改后的数组就是 [1, 2, 1, 2, 1, 2]。
然后，请你返回修改后的数组中的最大的子数组之和。
注意，子数组长度可以是 0，在这种情况下它的总和也是 0。
由于 结果可能会很大，所以需要 模（mod） 10^9 + 7 后再返回。 
示例 1：
输入：arr = [1,2], k = 3
输出：9
示例 2：
输入：arr = [1,-2,1], k = 5
输出：2
示例 3：
输入：arr = [-1,-2], k = 7
输出：0
提示：
1 <= arr.length <= 10^5
1 <= k <= 10^5
-10^4 <= arr[i] <= 10^4
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/k-concatenation-maximum-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class k次串联后的最大子数组之和 {
    /*
    * 利用 kadane 算法
    * kadane 算法用于求 最大子数组和
    * 我们一般是计算以当前元素作为数组的头元素，计算子数组的和，这样很难利用到之前计算过的信息
    * 所以 kadane 就改变思维，以当前元素作为数组的结尾元素，来计算子数组的和（子数组也要以当前元素结尾）
    * 那么就可以利用到之前的计算结果了。
    * 有两种可能：
    * 当前元素+之前元素的最大子数组和 > 当前元素的值
    * 那么 当前元素的最大子数组和 就是 之前元素的最大子数组和+当前元素的值
    * 如果小于的话，那么当前元素的最大子数组和就是自身
    * 这意味着，重新开始了一个数组 ----> 所以无论哪种情况，当前元素的最大子数组都是和下一个元素连续的。
    * 可以得到式子  maxNum = Math.max(maxPre+arr[i],arr[i])
    * 但是这道题目又有一点不同，就是数组可以重复k次，那如果我们直接计算重复k次后的数组的最大子数组和，未免太过费时
    * 可以观察到，如果数组的和>0 ，那么一个重复了k次的数组，它的最大值应该是 原始数组中的最大子数组和+k-1次的原始数组之和
    * 假设一个数组 重复2次  数组为：[-12,-10,55,66,-17,-18]  在原始数组中它的最大值为：55+66 = 121
    * 而重复 2 次后，数组为[-12,-10,55,66,-17,-18,-12,-10,55,66,-17,-18] ，那么最大值应该为
    * [-12,-10,{(55,66),-17,-18,-12,-10,55,66},-17,-18] 我们可以看到 是 55,66 + 一个原始数组 形成的
    * 其实就是看原始数组能否给我们的结果带来正面的结果
    * */
    public int kConcatenationMaxSum(int[] arr, int k) {
        int maxSum = 0;
        int maxPre = 0;
        int sum = 0;
        for(int i=0;i<Math.min(k,2)*arr.length;i++){
            maxPre = Math.max(maxPre+arr[i%arr.length],arr[i%arr.length]);
            maxSum = Math.max(maxSum,maxPre);
            if(i<arr.length){
                sum += arr[i];
            }
        }
        //判断原始数组是否能带来正结果
        while(sum>0&&--k>=2){
            maxSum = sum+maxSum;
        }
        return maxSum;
    }
}
